package com.wcj.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class dfs遍历图 {

}
// 无向图
class Graph3 {
    // 邻接矩阵法：适用于稠密图
    private final int maxVertices = 20;
    private Vertex vertexList[];
    private int adjMatrix[][];
    private int vertexCount;
    private Stack<Integer> theStack;
    private Queue<Integer> theQueue;
    public Graph3(){
        vertexList = new Vertex[maxVertices];
        adjMatrix = new int[maxVertices][maxVertices];
        vertexCount = 0;
        for (int y = 0; y < maxVertices; y++){
            for (int x = 0; x < maxVertices; x++){
                adjMatrix[x][y] = 0;
            }
        }
        theStack = new Stack();
        theQueue = new LinkedList<>();
    }

    public void addVertex(char lab){
        vertexList[vertexCount++] = new Vertex(lab);
    }

    public void addEdge(int i, int j){
        if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount){
            adjMatrix[i][j] = 1;
            adjMatrix[j][i] = 1;
        }
    }

    public void removeEdge(int i, int j){
        if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount){
            adjMatrix[i][j] = 0;
            adjMatrix[j][i] = 0;
        }
    }

    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    //深度优先遍历整个图
    public void dfs() {
        vertexList[0].visited = true;
        displayVertex(0);
        theStack.push(0);
        while (!theStack.isEmpty()) {
            int v = getAdjUnvisitedVertex(theStack.peek());
            // 返回-1说明这条这个顶点可以到达的下一个顶点全部被访问过了
            if (v == -1) {
                theStack.pop();
            }else {
                vertexList[v].visited = true;
                displayVertex(v);
                theStack.push(v);
            }
        }
        for (int j = 0; j < vertexCount; j++){
            vertexList[j].visited = false;
        }
    }

    private int getAdjUnvisitedVertex(int v) {
        // 拿到指定顶点，第一个没有被访问过的顶点
        for (int j = 0; j < vertexCount; j++){
            if (adjMatrix[v][j] == 1 && vertexList[j].visited == false){
                return j;
            }
        }
        return -1;
    }

    private void bfs() {
        vertexList[0].visited = true;
        displayVertex(0);
        theQueue.offer(0);
        int v2;
        while (!theQueue.isEmpty()){
            int v1 = theQueue.remove();
            while ((v2 = getAdjUnvisitedVertex(v1)) != -1){
                vertexList[v2].visited = true;
                displayVertex(v2);
                theQueue.offer(v2);
            }
        }
        for (int j = 0; j < vertexCount; j++){
            vertexList[j].visited = false;
        }
    }
}

class Vertex {
    public char label;
    public boolean visited;

    public Vertex(char label) {
        this.label = label;
    }
}
